package sorting.algorithms;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * QuickSort
 * @author geertweening
 */

public class QuickSort implements SortingAlgorithm{
	
	@Override
	public List<Comparable> sort(List<Comparable> toSort) {
		List<Comparable> result;
		if ( toSort.size() < 2){
			result = toSort;
		} else {
			List<Comparable> low = new ArrayList<Comparable>();
			List<Comparable> high = new ArrayList<Comparable>();
			int pivotIndex = toSort.size() / 2;
			Comparable pivot = toSort.get(pivotIndex);
			Comparable c;
			for (int i = 0; i < toSort.size(); i++){
				if (i != pivotIndex){
					c = toSort.get(i);
					if (c.compareTo(pivot) > 0){
						high.add(c);
					} else {
						low.add(c);
					}
				}
			}
			result = new ArrayList<Comparable>();
			result.addAll(sort(low));
			result.add(pivot);
			result.addAll(sort(high));
		}
		return result;
	}
	
	@Override
	public String getName() {
		// TODO Auto-generated method stub
		return "Quicksort";
	}
	
}
